package com.c2b.algorithm.leetcode.base;

import java.util.List;

/**
 * 通过删除字母匹配到字典里最长单词
 * <p>给你一个字符串s和一个字符串数组 dictionary ，找出并返回dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
 *
 * <p>如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。</p>
 *
 * @author c2b
 * @since 2022/5/25 17:51
 */
public class LC0524findLongestWord {


    /**
     * 通过删除字母匹配到字典里最长单词
     * <p>s 和 dictionary[i] 仅由小写英文字母组成
     *
     * @param s          字符串        1 <= s.length <= 1000
     * @param dictionary 字符串数组     1 <= dictionary.length <= 1000
     * @return java.lang.String
     * @author c2b
     * @since 2022/5/25 17:52
     */
    public String findLongestWord(String s, List<String> dictionary) {
        String ans = "";
        for (String dict : dictionary) {
            int indexS = 0;
            int indexD = 0;
            while (indexS < s.length() && indexD < dict.length()) {
                if (s.charAt(indexS) == dict.charAt(indexD)) {
                    indexD++;
                }
                indexS++;
            }
            if (indexD == dict.length()) {
                // 如果长度较大 或者 长度相等字典序较小
                if (dict.length() > ans.length() || (dict.length() == ans.length() && dict.compareTo(ans) < 0)) {
                    ans = dict;
                }
            }
        }
        return ans;
    }
}
